package com.example.leetcode;

/**
 * 最长回文子串
 * 中心扩散  动态规划
 */
public class Demo0005 {

    public static void main(String[] args) {

    }

    //中心扩散法
    public static String longestPalindrome01(String s) {
        int len = s.length();
        //长度小于2直接返回
        if (len<2){
            return s;
        }

        /**
         * 定义回文串起始位置
         * 定义长度
         */
        int start=0;
        int maxLen=0;

        for (int i = 0; i < len;) {

            //如果剩余长度不够子串的一半则直接返回
            if (len-i<maxLen/2){
                break;
            }

            //定义左右节点,并过滤重复字符串
            int left=i,right=i;
            while (right<len-1 && s.charAt(right)==s.charAt(right+1)){
                ++right;
            }

            //记录下次循环位置
            i=right+1;

            //当左指针等于右指针时指针可以左右扩散
            while (left>0 && right+1<len && s.charAt(left-1)==s.charAt(right+1)){
                ++right;
                --left;
            }

            //记录最大长度的起始值和长度
            if (right-left+1>maxLen){
                start=left;
                maxLen=right-left+1;
            }
        }
        return s.substring(start, start+maxLen);
    }

    //动态规划
    public static String longestPalindrome02(String s){
        int len = s.length();
        //边界条件
        if (len<2){
            return s;
        }

        /**
         * 定义起始位置
         * 定义子串长度
         * 定义全部情况数组
         */
        int start=0,maxLen=1;
        boolean[][] f=new boolean[len][len];
        for (int right = 1; right <len ; right++) {
            for (int left = 0; left < right; left++) {

                //否定条件
                if (s.charAt(left)!=s.charAt(right)){
                    f[left][right]=false;
                    continue;
                }

                //边界条件
                if ((right-left<3)){
                    f[left][right]=true;
                }else {
                    //转移方程
                    f[left][right]=f[left+1][right-1];
                }

                //判断是否最长
                if (f[left][right] && right-left+1>maxLen){
                    start=left;
                    maxLen=right-left+1;
                }
            }
        }

        return s.substring(start, start+maxLen);
    }
}
